/*
 ------------------------------------------------------------------------------
 Copyright (C) 2013 Eternal Games.

 This file is part of the GLQuake source code.

 The GLQuake source code is free software; you can redistribute it and/or
 modify it under the terms of the GNU General Public License as published by
 the Free Software Foundation; either version 2 of the License, or (at your
 option) any later version.

 The GLQuake source code is distributed in the hope that it will be useful,
 but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
 more details.

 You should have received a copy of the GNU General Public License along with
 the GLQuake source code; if not, write to the Free Software Foundation, Inc.,
 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
 ------------------------------------------------------------------------------
*/


//
// sg_clip.cpp - ...
//


#include "sg_local.h"


#define MAX_CLIP_SECTORS			8192
#define MAX_CLIP_SECTOR_DEPTH		12

struct clipSector_t {
	int						axis;				// -1 == terminal sector
	float					dist;

	clipSector_t *			children[2];

	etEntity *				entities;
};

static clipSector_t			sg_clipSectors[MAX_CLIP_SECTORS];
static int					sg_numClipSectors;


/*
 ==============================================================================

 CLIP SECTORS

 ==============================================================================
*/


/*
 ==================
 SG_CreateClipSector
 ==================
*/
static clipSector_t *SG_CreateClipSector (const glqBounds &bounds, glqVec3 &maxSector, int depth){

	clipSector_t	*sector;
	glqBounds		bounds1, bounds2;
	glqVec3			size;

	sector = &sg_clipSectors[sg_numClipSectors++];

	if (depth == MAX_CLIP_SECTOR_DEPTH){
		sector->axis = -1;
		sector->dist = 0.0f;

		sector->children[0] = NULL;
		sector->children[1] = NULL;

		sector->entities = NULL;

		size = bounds[1] - bounds[0];

		if (size[0] > maxSector[0])
			maxSector[0] = size[0];
		if (size[1] > maxSector[1])
			maxSector[1] = size[1];
		if (size[2] > maxSector[2])
			maxSector[2] = size[2];

		return sector;
	}

	size = bounds[1] - bounds[0];

	if (size[0] >= size[1] && size[0] >= size[2])
		sector->axis = 0;
	else if (size[1] >= size[0] && size[1] >= size[2])
		sector->axis = 1;
	else
		sector->axis = 2;

	sector->dist = (bounds[1][sector->axis] + bounds[0][sector->axis]) * 0.5f;

	bounds1 = bounds;
	bounds1[0][sector->axis] = sector->dist;

	bounds2 = bounds;
	bounds2[1][sector->axis] = sector->dist;

	sector->children[0] = SG_CreateClipSector(bounds1, maxSector, depth + 1);
	sector->children[1] = SG_CreateClipSector(bounds2, maxSector, depth + 1);

	sector->entities = NULL;

	return sector;
}

/*
 ==================
 SG_CreateClipSectors

 Builds a uniformly divided tree for the given world size
 ==================
*/
void SG_CreateClipSectors (){

	clipModel_t	*clipModel;
	glqBounds	bounds;
	glqVec3		size, maxSector;

	if (sg_numClipSectors)
		return;			// Already created

	// Get the clip model
	clipModel = glqCollision->RegisterModel("_worldMap");

	// Get the bounds
	glqCollision->GetModelBounds(clipModel, bounds);

	size = bounds[1] - bounds[0];

	G_Printf("Map bounds: %i x %i x %i\n", (int)size[0], (int)size[1], (int)size[2]);

	// Create the clip sectors
	maxSector.Clear();

	SG_CreateClipSector(bounds, maxSector, 0);

	G_Printf("Max clip sector: %i x %i x %i\n", (int)maxSector[0], (int)maxSector[1], (int)maxSector[2]);
}

/*
 ==================
 SG_ListClipSectors_f
 ==================
*/
static void SG_ListClipSectors_f (){

	clipSector_t	*sector;
	etEntity		*entity;
	int				i, count;

	for (i = 0, sector = sg_clipSectors; i < sg_numClipSectors; i++, sector++){
		count = 0;

		for (entity = sector->entities; entity; entity = entity->nextInClipSector)
			count++;

		if (!count)
			continue;

		G_Printf("Sector %4i: %i entities\n", i, count);
	}
}

/*
 ==================
 SG_InitClipSectors
 ==================
*/
void SG_InitClipSectors (){

	// Add commands
	glqCmdSystem->AddCommand("listClipSectors", SG_ListClipSectors_f, "Lists clip sectors", NULL);
}

/*
 ==================
 SG_ShutdownClipSectors
 ==================
*/
void SG_ShutdownClipSectors (){

	// Remove commands
	glqCmdSystem->RemoveCommand("listClipSectors");

	// Clear the clip sectors
	glqMemory->Fill(sg_clipSectors, 0, sizeof(sg_clipSectors));

	sg_numClipSectors = 0;
}


/*
 ==============================================================================

 ENTITY LINKING

 ==============================================================================
*/


/*
 ==================
 
 ==================
*/
void SG_LinkEntity (etEntity *entity){

	clipSector_t	*sector;

	// Unlink from old position
	if (entity->isLinked)
		SG_UnlinkEntity(entity);

	// Compute the absolute bounds
	if (entity->currentAngles.IsCleared())
		entity->absBounds = entity->bounds + entity->currentOrigin;
	else
		entity->absBounds = entity->bounds.Transform(entity->currentOrigin, entity->currentAxis);

	// Because movement is clipped an epsilon away from an actual edge, we must
	// fully check even when bounding boxes don't quite touch
	entity->absBounds.ExpandSelf(BOX_EPSILON);

	// Get all the contacted leaves

	// Find the first clip sector that the entity's bounding box crosses
	sector = sg_clipSectors;

	while (1){
		if (sector->axis == -1)
			break;		// Terminal sector

		// Go down the appropriate sides
		if (entity->absBounds[0][sector->axis] > sector->dist){
			sector = sector->children[0];
			continue;
		}
		if (entity->absBounds[1][sector->axis] < sector->dist){
			sector = sector->children[1];
			continue;
		}

		// Crosses the sector
		break;
	}

	// Link it in
	entity->isLinked = true;

	entity->clipSector = sector;
	entity->nextInClipSector = sector->entities;

	sector->entities = entity;
}

/*
 ==================
 SG_UnlinkEntity
 ==================
*/
void SG_UnlinkEntity (etEntity *entity){

	clipSector_t	*sector;
	etEntity		*scan;

	entity->isLinked = false;

	sector = entity->clipSector;
	if (!sector)
		return;		// Not linked in anywhere

	entity->clipSector = NULL;

	if (sector->entities == entity){
		sector->entities = entity->nextInClipSector;
		return;
	}

	for (scan = sector->entities; scan; scan = scan->nextInClipSector){
		if (scan->nextInClipSector == entity){
			scan->nextInClipSector = entity->nextInClipSector;
			return;
		}
	}
}


/*
 ==============================================================================

 ENTITY CLIPPING

 ==============================================================================
*/


/*
 ==================
 
 ==================
*/
int SG_Contents (const glqVec3 &point, const glqBounds &bounds, int contentMask, bool skipAnimations, int passEntityNum){

	return 0;
}

/*
 ==================
 
 ==================
*/
int SG_EntityContents (etEntity *entity, const glqVec3 &point, const glqBounds &bounds, int contentMask, bool skipAnimations){

	return 0;
}

/*
 ==================
 
 ==================
*/
void SG_Trace (const glqVec3 &start, const glqVec3 &end, const glqBounds &bounds, int contentMask, bool skipAnimations, int passEntityNum, trace_t *trace){

}